package backTrack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Class77 {

    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> curList=new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return   result;
    }

    public  void backtracking(int n,int k,int startIndex) {
        if (curList.size()==k) {
            result.add(new ArrayList<>(curList));
            return;
        }
        for (int i=startIndex;i <= n - (k - curList.size()) + 1;i++) {
            curList.add(i);
            backtracking(n,k,i+1); // 递归
            curList.removeLast();
        }
    }

    public static void main(String[] args) {
        Class77 class77 = new Class77();
        System.out.println(class77.combine(4, 4).size());
    }

}
